package org.codetranslators.common;

import java.util.*;

import org.codetranslators.compiler.intermrep.AssemblyInstruction;
import org.codetranslators.compiler.intermrep.CJump;
import org.codetranslators.compiler.intermrep.LabelInstr;
//import org.codetranslators.compiler.liveness.CfgProperties;
//import org.codetranslators.compiler.liveness.Node;
import org.codetranslators.common.Node;
import org.codetranslators.common.Temp;

import sun.rmi.transport.proxy.CGIHandler;

public class ControlFlowGraph extends DiGraph{

	private Vector<Object> quadruples;  // This list represents the originial list of all instructions that
								// are yet to be transformed for optimization;
	private ArrayList<NodeInfo> nodesInfo;
	ArrayList<String> labels;
	ControlFlowNode startNode;
	ControlFlowNode endNode;
	Vector<Temp> tempsSet;

	public ControlFlowGraph(){}

	public ControlFlowGraph(Vector assemInsts, boolean oneInstructionPerBlock){
		quadruples = assemInsts;
		tempsSet = new Vector<Temp>();

		if(oneInstructionPerBlock)
			createGraphWithSingleInstrPerBlock();
		else
			createGraphWithMultipleInstrsPerBlock();

		displayFlowGraph();
	}

	public ControlFlowGraph(ArrayList<NodeInfo> xmlNodesInfo){
		nodesInfo = xmlNodesInfo;
//		labels = labels;
		createGraphWithXMLData();
		displayFlowGraph();
	}

	/*
	 * This method creates the graph with single instruction per basic block. This is typically used for
	 * creating interference graphs
	 */
	private void createGraphWithSingleInstrPerBlock(){
		int numIns = quadruples.size();
		initNodes(numIns);
		for(int i = 0; i < numIns; i++)
		{
			AssemblyInstruction instr = (AssemblyInstruction) quadruples.elementAt(i);
			Vector jumpsList = instr.getJumps();

			ControlFlowNode newInsNode = newNodeForSingleInstruction("" + i, instr);
			if(i == 0) startNode = newInsNode;

			if(jumpsList != null)
			{
				// This must be either a jump or a cjump
				int numJumps = jumpsList.size();
				for(int j = 0; j < numJumps; j++)
				{
					String jmpStr = (String) jumpsList.elementAt(j);
					ControlFlowNode nextNode = getNodeAfterLabel(jmpStr);

					Edge edge = new Edge(newInsNode, nextNode);
					addDirectedEdge(edge, newInsNode, nextNode);
				}
			}
			else
			{
				// This must be either a label or an operation
				if(i != numIns -1)
				{
					// Not the last instruction; get the next instruction and add and edge
					ControlFlowNode nextNode = getNodeForNextNonLabelInstr(i);
					if(nextNode != null) {
						Edge edge = new Edge(newInsNode, nextNode);
						addDirectedEdge(edge, newInsNode, nextNode);
					}
				}
			}
		}
	}

	/*
	 * This method creates the graph with multiple instructions per basic block. This is typically used for
	 * optimizations
	 */
	private void createGraphWithMultipleInstrsPerBlock()
	{
		int numIns = quadruples.size();
		LinkedHashMap<String, ControlFlowNode> labelStrVsNodes = new LinkedHashMap<String, ControlFlowNode>();   // Map of label string versus the corresponding cf node
		HashMap nodeVsNextLabel = new HashMap();   // Map of

		Vector quadruplesInNode = new Vector();
		ControlFlowNode controlFlowNode = new ControlFlowNode();
		String currentLabel = "";
		int nodeCount = 0;
		boolean lastInstrIsJump = false;
		for(int i = 0; i < numIns; i++){
			// Get the quadruple and add the variables (temporaries) in the quadruple to
			// the list of temporaries
			AssemblyInstruction instr = (AssemblyInstruction) quadruples.elementAt(i);
			addToTempList(instr.getSrcList());
			addToTempList(instr.getDestList());

			Vector jumpsList = instr.getJumps();
			String labelStr = instr.getLabelStr();
			if(jumpsList != null)
			{
				// This must be either a jump or a cjump
				// Set the list of quadruples created so far into the current flow node
				quadruplesInNode.addElement(instr);
				controlFlowNode.setInstructions(quadruplesInNode);
				//labelStrVsNodes.put(currentLabel, controlFlowNode);

				quadruplesInNode = new Vector();
				lastInstrIsJump = true;
			}
			else if(labelStr != null){
				// This is a label
				if(!lastInstrIsJump) {
					if(nodeCount != 0) {    // Not the first label
						nodeVsNextLabel.put(controlFlowNode, labelStr);
						// End the previous list of quadruples and put them in the current node
						controlFlowNode.setInstructions(quadruplesInNode);
						//labelStrVsNodes.put(currentLabel, controlFlowNode);
					}
				}

				// Create a new control flow node
				controlFlowNode = new ControlFlowNode();
				controlFlowNode.setName(labelStr);
				quadruplesInNode = new Vector();
				quadruplesInNode.addElement(instr);
				controlFlowNode.setInstructions(quadruplesInNode);
				if(nodeCount == 0) startNode = controlFlowNode;
				addNode(controlFlowNode);
				currentLabel = labelStr;
				labelStrVsNodes.put(currentLabel, controlFlowNode);

				lastInstrIsJump = false;   // Set the lastInstrIsJump to false
				nodeCount++;               // Increment the node count
			}
			else {
				// Neither a label nor a jump
				quadruplesInNode.addElement(instr);
				lastInstrIsJump = false;
			}
		}

		// Iterate through the HashMap created above to create the control flow graph
		Set entries = labelStrVsNodes.entrySet();
		Iterator iter = entries.iterator();
		nodeCount = 0;
		while(iter.hasNext())
		{
			Map.Entry entry = (Map.Entry) iter.next();
			ControlFlowNode cfNode = (ControlFlowNode) entry.getValue();

			// Get the last last quadruple in the list of quadruples for this node
			Vector quads = cfNode.getInstructions();
			AssemblyInstruction instr = (AssemblyInstruction)quads.lastElement();
			Vector jumpsList = instr.getJumps();
			if(jumpsList != null){
				// The last quadruple in the current node is a jump statement; create and add edges
				// to the current node for the targets in the jump
				int numJumps = jumpsList.size();
				for(int i = 0; i < numJumps; i++) {
					String jmpStr = (String) jumpsList.elementAt(i);
					ControlFlowNode targetNode = (ControlFlowNode) labelStrVsNodes.get(jmpStr);
					Edge edge = new Edge(cfNode, targetNode);
					addDirectedEdge(edge, cfNode, targetNode);
				}
			}
			else {
				// The last quadruple in the current node is not a jump statement; the target must be the
				// logical next node in the flow; get it from the map of node against the next label
				String nextLabel = (String) nodeVsNextLabel.get(cfNode);
				ControlFlowNode targetNode = (ControlFlowNode) labelStrVsNodes.get(nextLabel);
				if(targetNode != null) {
					Edge edge = new Edge(cfNode, targetNode);
					addDirectedEdge(edge, cfNode, targetNode);
				}
			}
		}

		// Go through the list of nodes and identify the end node; this will be the only node
		// with no successors

		for(int a = 0; a < getNumNodes(); a++){
			ControlFlowNode node = (ControlFlowNode)getNode(a);
			if(node.getNumOutgoingEdges() == 0){
				endNode = node;
				break;
			}
		}
	}

	private ControlFlowNode getNodeAfterLabel(String jmpStr)
	{
		int numIns = quadruples.size();
		ControlFlowNode nodeAfterLabel = null;
		for(int i = 0; i < numIns; i++)
		{
			AssemblyInstruction instr = (AssemblyInstruction) quadruples.elementAt(i);
			String lblFound = instr.getLabelStr();   // can be null
			if(jmpStr.equals(lblFound))
			{
				if(i == numIns -1){  // The last instruction; return it
					nodeAfterLabel =  newNodeForSingleInstruction(""+i, instr);
				}
				else{
					instr = (AssemblyInstruction) quadruples.elementAt(i +1);
					nodeAfterLabel =  newNodeForSingleInstruction("" + (i + 1), instr);
				}
				break;
			}
		}
		return nodeAfterLabel;
	}

	private ControlFlowNode newNodeForSingleInstruction(String name, AssemblyInstruction instr)
	{
		// Check if this node has already been created by comparing with the name passed with the
		// names of the node currently present in this graph

		int numNodes = getNumNodes();
		for(int i = 0; i < numNodes; i++){
			ControlFlowNode cfNodePresent = (ControlFlowNode) getNode(i);
			if(cfNodePresent != null && name.equals(cfNodePresent.getName())){
				return cfNodePresent;
			}
		}

		// This node has not been created yet; create this node
		ControlFlowNode newInsNode =new ControlFlowNode();
		newInsNode.setName(name);
		Vector srcList = instr.getSrcList();
		Vector destList = instr.getDestList();
		addToTempList(srcList);
		addToTempList(destList);

		// In a control flow graph with one statement per basic block, the list of
		// instructions will contain only one instruction.
		Vector<AssemblyInstruction> instructions = new Vector<AssemblyInstruction>();
		instructions.add(instr);

		// Set the (only) instruction to the node
		newInsNode.setInstructions(instructions);

		//addNode(newInsNode);    // Add the new node to this graph
		addNodeAt(newInsNode , Integer.parseInt(name));    // Add the new node to this graph

		return newInsNode;
	}

	/* Returns the next non-label instruction and creates it if required
	 *
	 */
	private ControlFlowNode getNodeForNextNonLabelInstr(int n)
	{
		ControlFlowNode nextNode = null;

		int numIns = quadruples.size();
		for(int i = n+1; i < numIns; i++)
		{
			AssemblyInstruction instr = (AssemblyInstruction) quadruples.elementAt(i);
			if(instr.getLabelStr() == null)
			{
				// This is a non-label instruction; create a new node for this and return
				nextNode = newNodeForSingleInstruction("" +i, instr);
				break;
			}
		}
		return nextNode;
	}

	private void addToTempList(Vector list)
	{
		if(list == null) return;
		int numTemps = list.size();
		for(int i = 0; i < numTemps; i++)
		{
			Temp tmp = (Temp)list.elementAt(i);
			if(!tempsSet.contains(tmp))
				tempsSet.addElement(tmp);
		}
	}

	public ControlFlowNode getStartNode() {
		return startNode;
	}

	public ControlFlowNode getEndNode() {
		return endNode;
	}

	public Vector getQuadruples() {
		//return quadruples;
		Vector<AssemblyInstruction> quads = new Vector<AssemblyInstruction>();
		
		//Start with the start node
		HashSet<ControlFlowNode> visitedNodes = new HashSet<ControlFlowNode>();
		int numNodes = getNumNodes();
		boolean start = true;
		ControlFlowNode currentNode = null;
		while(visitedNodes.size() != numNodes){
			if(start){
				currentNode = startNode;
				Vector<AssemblyInstruction> instrsInNode = startNode.getInstructions();
				quads.addAll(instrsInNode);
				visitedNodes.add(startNode);
			}
			
			// Get the last instruction in the current node
			Vector<AssemblyInstruction> instrsInNode = currentNode.getInstructions();
			AssemblyInstruction lastInstr = instrsInNode.elementAt(instrsInNode.size() -1);
			int lastInstrType = lastInstr.getType();
			if(lastInstrType == AssemblyInstruction.CJUMP){
				CJump cjump = (CJump) lastInstr;
				String trueLbl = cjump.getTrueLabel();
				String falseLbl = cjump.getFalseLabel();
				
				// Identify the node for the "false" path
				Vector<Node> children = currentNode.getSuccessors();
				ControlFlowNode nodeForFalse = null;
				ControlFlowNode nodeForTrue = null;
				for(int i = 0; i < children.size(); i++){
					ControlFlowNode cfChildNode = (ControlFlowNode) children.elementAt(i);
					Vector<AssemblyInstruction> childNodeIns = cfChildNode.getInstructions();
					AssemblyInstruction firstInstr = childNodeIns.elementAt(0);
					LabelInstr lblInstr = (LabelInstr) firstInstr; // First instr. must be a label
					String lblName = lblInstr.getLabelStr();
					if(falseLbl.equals(lblName)){
						nodeForFalse = cfChildNode;
					}
					if(trueLbl.equals(lblName)){
						nodeForTrue = cfChildNode;
					}
				}
				
				// Add the "if" and the "else" cf nodes
				if(visitedNodes.add(nodeForFalse)){
					quads.addAll(nodeForFalse.getInstructions());
				}
				if(visitedNodes.add(nodeForTrue)){
					quads.addAll(nodeForTrue.getInstructions());
				}
				
				// Update the current node
			}
			else if(lastInstrType == AssemblyInstruction.JUMP){
				
			}
			else{
			}
		}
			
		
		return quads;
	}

	public Vector<Temp> getVariables() {
		return tempsSet;
	}

	public void setEndNode(ControlFlowNode node){
		endNode = node;
	}

	public void setStartNode(ControlFlowNode node){
		startNode = node;
	}

	/*
	 * This function returns a node with the name passed as parameter, if it exists in this graph
	 * instance. Note that this does not consider object equivalence. If there is no such node
	 * with the same name as that of the parameter, it returns null
	 */
	public ControlFlowNode getNodeWithName(String nodeName){
		for(int i = 0; i < getNumNodes(); i++){
			ControlFlowNode nd = (ControlFlowNode) getNode(i);
			if(nd.getName().equals(nodeName))
				return nd;
		}
		return null;
	}

	/*
	 * This function returns the control flow node in which a instruction (quadruple) exists. Note
	 * that this function considers object references for comparison
	 *
	 */
	public ControlFlowNode getCFNodeForQuadruple(AssemblyInstruction instr){
		int numNodes = getNumNodes();
		for(int i = 0; i < numNodes; i++){
			ControlFlowNode nd = (ControlFlowNode) getNode(i);
			Vector quadruples = nd.getInstructions();
			for(int j = 0; j < quadruples.size(); j++){
				AssemblyInstruction instrInNode = (AssemblyInstruction) quadruples.elementAt(j);
				if(instrInNode == instr)
					return nd;
			}
		}
		return null;
	}

	public BitSet getUsesBitVector(ControlFlowNode node){
		return getBitVector(node, true);
	}

	public BitSet getDefsBitVector(ControlFlowNode node){
		return getBitVector(node, false);
	}

	private BitSet getBitVector(ControlFlowNode node, boolean forUses)
	{
		BitSet bitSet = null;

		AssemblyInstruction instr = (AssemblyInstruction) node.getInstructions().elementAt(0);

		if(forUses)
			bitSet = node.getUsesBitVector();
		else
			bitSet = node.getDefsBitVector();

		if(bitSet != null) return bitSet;

		// Not been calculated so far; calculate it
		Vector list = null;
		if(forUses)
			list = instr.getSrcList();
		else
			list = instr.getDestList();

		bitSet = new BitSet(tempsSet.size());
		bitSet.clear();

		if(list == null) return bitSet;  // No uses or defs for this node

		for(int i = 0; i < list.size(); i++)
		{
			Temp temp = (Temp) list.elementAt(i);
			int index = tempsSet.indexOf(temp);
			bitSet.set(index);
		}

		if(forUses)
			node.setUsesBitVector(bitSet);
		else
			node.setDefsBitVector(bitSet);

		return bitSet;
	}

	public Temp getTemp(int index){
		return (Temp)tempsSet.elementAt(index);
	}

	public void displayFlowGraph(){
		System.out.println("CONTROL FLOW GRAPH: ");
		display();
		int numNodes = getNumNodes();
		for(int i = 0; i < numNodes; i++){
			ControlFlowNode nd = (ControlFlowNode) getNode(i);
			if(nd == null) continue;
			if(nodesInfo!=null); else{nd.displayNode();}
		}
	}
	public void createGraphWithXMLData(){
		System.out.println("====createGraphWithXMLData===");
		int numIns = nodesInfo.size();
		System.out.println(numIns);
		LinkedHashMap<String, ControlFlowNode> labelStrVsNodes = new LinkedHashMap<String, ControlFlowNode>();   // Map of label string versus the corresponding cf node

    	ControlFlowNode controlFlowNode = new ControlFlowNode();
    	controlFlowNode.setFromXml(true);
    	ControlFlowNode lastControlFlowNode = new ControlFlowNode();
    	lastControlFlowNode.setFromXml(true);
    	ControlFlowNode targetNode = null;
		//String currentLabel = "";
		//int nodeCount = 0;

		boolean startNodeFound = false;
		boolean endNodeFound = false;
		ControlFlowNode startControlFlowNode = new ControlFlowNode();
		startControlFlowNode.setFromXml(true);

		for(int i = 0; i < numIns ; i++){
			System.out.println("entering for loop ----"+i);// finding first and last nodes ----> starting point and end point

			NodeInfo nodeInfo = nodesInfo.get(i);

			if(nodeInfo.isStartNode()){ // finding first node and adding to linkedhashmap
				System.out.println("starting node found");
				startNodeFound = true;
				//System.out.println("------");
				//System.out.println(nodeInfo.getInstrctionsInfo().size());
				controlFlowNode.setInstructions(new Vector(nodeInfo.getInstrctionsInfo()));
				System.out.println("--------- 0");
				controlFlowNode.setName(nodeInfo.getName());
				startControlFlowNode.setInstructions(new Vector(nodeInfo.getInstrctionsInfo()));
				startControlFlowNode.setName(nodeInfo.getName());

				System.out.println("--------- 1");
				addNode(controlFlowNode);
				System.out.println("--------- 2");
				labelStrVsNodes.put(nodeInfo.getName(), controlFlowNode);
				System.out.println("loop "+i);
			}
			else if(nodeInfo.isEndNode()){ // finding last node but not adding now
				System.out.println("end node found");
				endNodeFound = true;
		    	lastControlFlowNode.setInstructions(new Vector(nodeInfo.getInstrctionsInfo()));
		    	lastControlFlowNode.setName(nodeInfo.getName());
		    }
			/*else if(startNodeFound && endNodeFound){
				System.out.println("both nodes found");
				break;
			}*/
			System.out.println("loop count "+i);

		}

		for(NodeInfo nodeInfo: nodesInfo){
			System.out.println("adding all nodes");// adding all nodes to hashmap
			if(nodeInfo.isStartNode() || nodeInfo.isEndNode())
				continue;
			controlFlowNode = new ControlFlowNode();
			controlFlowNode.setFromXml(true);
			controlFlowNode.setInstructions(new Vector(nodeInfo.getInstrctionsInfo()));
			controlFlowNode.setName(nodeInfo.getName());
			addNode(controlFlowNode);
			labelStrVsNodes.put(nodeInfo.getName(), controlFlowNode);
		}
		addNode(lastControlFlowNode);
		labelStrVsNodes.put(lastControlFlowNode.getName(), lastControlFlowNode); // adding last node which is found previously

		Set entries = labelStrVsNodes.entrySet();
		Iterator iter = entries.iterator();
		//nodeCount = 0;
		while(iter.hasNext())
		{
			System.out.println("no of times");
			Map.Entry entry = (Map.Entry) iter.next();
			ControlFlowNode cfNode = (ControlFlowNode)entry.getValue();
			System.out.println("finding for "+cfNode.getName());
			for(NodeInfo ndInfo : nodesInfo){
				System.out.println("loop no");
				if(cfNode.getName().equals(ndInfo.getName()) && ndInfo.getLeftChilds()!=null && ndInfo.getLeftChilds().size()>0){
					System.out.println("enter into if leftchilds");


					NodeInfo leftNode = null;
					for(NodeInfo localTargetNode: nodesInfo){
						if(localTargetNode.getId() == ndInfo.getLeftChilds().get(0)){
							leftNode = localTargetNode;
							System.out.println("left child of "+ndInfo.getName()+" is "+leftNode.getName());
						}
					}

					if(labelStrVsNodes.get(leftNode.getName())!=null){
						System.out.println("yes finded in the label String vs Nodes linked hash map");
						targetNode = new ControlFlowNode();
						targetNode = labelStrVsNodes.get(leftNode.getName());
					}
					else{
						System.out.println("not finded in linked hash map");
					}

					if(leftNode != null){
						System.out.println("adding left edge");

						//targetNode.setName(leftNode.getName());
						//targetNode.setInstructions(new Vector(leftNode.getInstrctionsInfo()));
						Edge edge = new Edge(cfNode, targetNode);
						addDirectedEdge(edge, cfNode, targetNode);
					}
					else{
						System.out.println("no left node"+cfNode.getName());
					}
				}
				if(cfNode.getName().equals(ndInfo.getName()) && ndInfo.getRightChilds()!=null && ndInfo.getRightChilds().size()>0){
					System.out.println("enter into if rightchilds");
					NodeInfo rightNode = null;
					for(NodeInfo localTargetNode: nodesInfo){
						if(localTargetNode.getId() == ndInfo.getRightChilds().get(0)){
							rightNode = localTargetNode;
							System.out.println("right child of "+ndInfo.getName()+" is "+rightNode.getName());
						}
					}

					if(labelStrVsNodes.get(rightNode.getName())!=null){
						System.out.println("yes finded in the label String vs Nodes linked hash map");
						targetNode = new ControlFlowNode();
						targetNode = labelStrVsNodes.get(rightNode.getName());
					}
					else{
						System.out.println("not finded in linked hash map");
					}

					if(rightNode != null){
						System.out.println("adding right edge");
						//targetNode = new ControlFlowNode();
						//targetNode.setName(rightNode.getName());
						//targetNode.setInstructions(new Vector(rightNode.getInstrctionsInfo()));
						Edge edge = new Edge(cfNode, targetNode);
						addDirectedEdge(edge, cfNode, targetNode);
					}
					else{
						System.out.println("no right node"+cfNode.getName());
					}
				}
			}

		}
		System.out.println("not here");
		//System.out.println("start node is "+startNode.getName());

		// Go through the list of nodes and identify the end node; this will be the only node
		// with no successors

		for(int a = 0; a < getNumNodes(); a++){
			ControlFlowNode node = (ControlFlowNode)getNode(a);
			System.out.println("label name"+node.getName());
			if(node.getNumOutgoingEdges() == 0){
				endNode = node;
				//break;
			}
			if(node.getNumIncomingEdges()==0){
				startNode = node;
				System.out.println("found start node");
			}
		}
	}

	public int numberOfNodes() {
		// TODO Auto-generated method stub
		return getNumNodes();
	}

	public Node firstNode() {
		return getStartNode();
	}
}

